package acwing.算法进阶打卡;/**
 * @author： li
 * @date： 2022-03-13 16:39
 * @version 1.0
 */
/*从 1∼n 这 n 个整数中随机选出 m 个，输出所有可能的选择方案。

输入格式
两个整数 n,m ,在同一行用空格隔开。

输出格式
按照从小到大的顺序输出所有方案，每行 1 个。

首先，同一行内的数升序排列，相邻两个数用一个空格隔开。

其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面（例如 1 3 5 7 排在 1 3 6 8 前面）。

数据范围
n>0 ,
0≤m≤n ,
n+(n−m)≤25*/
import java.util.*;

public class 递归实现组合型枚举{
    static int n;
    static int m;
    //用二进制状态压缩,也就是用二进制上的位来记录数有没有被用过。
// u是当前枚举到的数，state是二进制数记录哪些数被选
    static void dfs(int u ,int sum,int state){
        if(sum==m){
//            System.out.println(state);
            for(int i = 0; i< n; i++)
                //判断第i位是不是1，如果是1就代表被选，输出
                if(((state >> i )& 1)==1){
                    //第几位就代表输出几，只不过不是从0开始，而是从1开始
                    System.out.print((i+1)+" ");
                }
            System.out.println(" ");
            return;
        }
        if( u == n) return;//总递归数
        // 用这个数，把第u位变成1
        // 运算优先级： 左移高于位运算|
        //根据题意要先将低位进行标记
        dfs(u + 1,sum+1, state | 1 << u);
        // 不用这个数，第u位不动
        dfs(u + 1,sum,state);

    }
    public static void main(String[] args) {
        Scanner in =new Scanner(System.in);
        n = in.nextInt();
        m= in.nextInt();
    /*
    回顾一下dfs参数的含义：
        - u是当前枚举到的数，
        -state是二进制数记录哪些数被选
    则 dfs(0, 0)表示：当前枚举到0，没有数被选

    */
        dfs(0, 0,0);

        in.close();
    }
}